/*
 * @Author: szx
 * @Date: 2022-03-12 13:28:28
 * @LastEditTime: 2022-03-12 13:32:46
 * @Description:
 * @FilePath: \leetcode\1-99\40\40_2.js
 */
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
    const res = [];
    candidates.sort((a, b) => a - b);
    const visited = new Array(candidates.length).fill(false);
    const backtrace = (path, sum, index) => {
        if (sum > target) return;
        if (sum === target) {
            res.push(Array.from(path));
            return;
        }
        for (let i = index; i < candidates.length; i++) {
            if (i >= 1 && candidates[i] == candidates[i - 1] && !visited[i - 1]) continue;
            visited[i] = true;
            path.push(candidates[i]);
            backtrace(path, sum + candidates[i], i + 1);
            path.pop();
            visited[i] = false;
        }
    };
    backtrace([], 0, 0);
    return res;
};
console.log(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8));
